package leetcode_git;

import java.util.Scanner;

/**
 * @author huangxiaoming
 * @date 2022/6/3
 **/
public class Test5 {

    /**
     * 题目描述：假设农场中成熟的母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量。
     * @param args
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            System.out.println(rob(n));
        }
    }

    private static int rob(int n) {
        if (n < 4) return n;
        int[] dp = new int[n+1];
        // 起始条件
        for (int i = 0; i < 4; ++i) {
            dp[i] = i;
        }
        // 从第4年才满足状态转移方程
        for (int i = 4; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 3];
        }
        return dp[n];
    }
}
